#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char ElementType;

typedef struct TreeNode
{
    char data;
    struct TreeNode *lChild;
    struct TreeNode *rChild;
} TreeNode, *BitTree;

typedef struct QNode
{
    void *data;
    struct QNode *next;
} QNode;

typedef struct Queue
{
    QNode *front;
    QNode *rear;
} Queue;

typedef struct SNode
{
    void *data;
    struct SNode *next;
} SNode, *Stack;

void InitStack(Stack &stack)
{
    stack = (SNode *)malloc(sizeof(SNode));
    stack->next = NULL;
}

bool EmptyStack(Stack stack)
{
    return stack->next == NULL;
}

void StackPush(Stack stack, void *data)
{
    SNode *node = (SNode *)malloc(sizeof(SNode));
    node->data = data;
    node->next = stack->next;
    stack->next = node;
}

void *StackPop(Stack stack)
{
    if (EmptyStack(stack))
    {
        return NULL;
    }
    SNode *node = stack->next;
    void *data = node->data;
    stack->next = node->next;
    free(node);
    return data;
}

void InitQueue(Queue &queue)
{
    queue.front = queue.rear = (QNode *)malloc(sizeof(QNode));
    queue.front->next = NULL;
}

bool EmptyQueue(Queue queue)
{
    return queue.front == queue.rear;
}

void EnQueue(Queue &queue, void *data)
{
    QNode *node = (QNode *)malloc(sizeof(QNode));
    node->data = data;
    node->next = NULL;
    queue.rear->next = node;
    queue.rear = node;
}

void *DeQueue(Queue &queue)
{
    if (EmptyQueue(queue))
    {
        return NULL;
    }
    QNode *node = queue.front->next;
    void *data = node->data;
    queue.front->next = node->next;
    free(node);
    if (queue.front->next == NULL)
    {
        queue.rear = queue.front;
    }
    return data;
}

BitTree BuildTree(char *ch, int len)
{
    if (len == 0)
    {
        return NULL;
    }
    BitTree root_tree = (BitTree)malloc(sizeof(BitTree));
    root_tree->data = ch[0];
    root_tree->lChild = NULL;
    root_tree->rChild = NULL;
    TreeNode *cur_tree_node = root_tree;
    Queue queue;
    InitQueue(queue);
    for (int index = 1; index < len; index++)
    {
        TreeNode *tree_node = (TreeNode *)malloc(sizeof(TreeNode));
        tree_node->data = ch[index];
        tree_node->lChild = NULL;
        tree_node->rChild = NULL;
        if (cur_tree_node->lChild && cur_tree_node->rChild)
        {
            cur_tree_node = (TreeNode *)DeQueue(queue);
        }
        if (!cur_tree_node->lChild)
        {
            cur_tree_node->lChild = tree_node;
        }
        else
        {
            cur_tree_node->rChild = tree_node;
        }
        EnQueue(queue, tree_node);
    }
    return root_tree;
}

void BFS(BitTree tree)
{
    Queue queue;
    InitQueue(queue);
    EnQueue(queue, tree);
    while (!EmptyQueue(queue))
    {
        TreeNode *tmp_tree_node = (TreeNode *)DeQueue(queue);
        printf("%2c", tmp_tree_node->data);
        if (tmp_tree_node->lChild)
        {
            EnQueue(queue, tmp_tree_node->lChild);
        }
        if (tmp_tree_node->rChild)
        {
            EnQueue(queue, tmp_tree_node->rChild);
        }
    }
}

void PreOrderTree(BitTree tree)
{
    if (tree)
    {
        printf("%2c", tree->data);
        PreOrderTree(tree->lChild);
        PreOrderTree(tree->rChild);
    }
}

void PreOrderTreeV2(BitTree tree)
{
    Stack stack;
    InitStack(stack);
    StackPush(stack, tree);
    while (!EmptyStack(stack))
    {
        TreeNode *tmp_tree_node = (TreeNode *)StackPop(stack);
        printf("%2c", tmp_tree_node->data);
        if (tmp_tree_node->rChild)
        {
            StackPush(stack, tmp_tree_node->rChild);
        }
        if (tmp_tree_node->lChild)
        {
            StackPush(stack, tmp_tree_node->lChild);
        }
    }
}

// 非递归先序遍历二叉树
void PreOrderTree2(BitTree tree)
{
    Stack stack;
    BitTree treeNode = tree;
    InitStack(stack);
    while (!EmptyStack(stack) || treeNode)
    {
        if (treeNode)
        {
            printf("%2c", treeNode->data);
            StackPush(stack, treeNode);
            treeNode = treeNode->lChild;
        }
        else
        {
            treeNode = (TreeNode *)StackPop(stack);
            treeNode = treeNode->rChild;
        }
    }
    printf("\n");
}

void DFS(BitTree tree)
{
    Stack stack;
    InitStack(stack);
    TreeNode *treeNode = tree;
    while (!EmptyStack(stack) || treeNode)
    {
        if (!treeNode)
        {
            treeNode = (TreeNode *)StackPop(stack);
            treeNode = treeNode->rChild;
        }
        else
        {
            printf("%2c", treeNode->data);
            StackPush(stack, treeNode);
            treeNode = treeNode->lChild;
        }
    }
    printf("\n");
}

void MidOrderTree(BitTree tree)
{
    if (tree)
    {
        MidOrderTree(tree->lChild);
        printf("%2c", tree->data);
        MidOrderTree(tree->rChild);
    }
}

void MidOrderTree2(BitTree tree)
{
    Stack stack;
    InitStack(stack);
    TreeNode *treeNode = tree;
    while (!EmptyStack(stack) || treeNode)
    {
        if (!treeNode)
        {
            treeNode = (TreeNode *)StackPop(stack);
            printf("%2c", treeNode->data);
            treeNode = treeNode->rChild;
        }
        else
        {
            StackPush(stack, treeNode);
            treeNode = treeNode->lChild;
        }
    }
    printf("\n");
}

void PostOrderTree(BitTree tree)
{
    if (tree)
    {
        PostOrderTree(tree->lChild);
        PostOrderTree(tree->rChild);
        printf("%2c", tree->data);
    }
}

int main()
{
    ElementType ch[] = "abcdefghijklmno";
    BitTree tree = BuildTree(ch, 15);
    printf("\n--------------PreOrderTree-------------------\n");
    PreOrderTree(tree);
    printf("\n");
    PreOrderTreeV2(tree);
    printf("\n");
    PreOrderTree2(tree);
    printf("\n-------------MidOrderTree--------------------\n");
    MidOrderTree(tree);
    printf("\n");
    MidOrderTree2(tree);
    printf("\n-------------PostOrderTree--------------------\n");
    PostOrderTree(tree);
    // PostOrderTreeV2(tree);
    printf("\n");
    printf("\n-------------BFSOrderTree--------------------\n");
    BFS(tree);
    printf("\n");
    printf("\n-------------DFSOrderTree--------------------\n");
    DFS(tree);
    printf("\n");

    return 0;
}